home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / bmgrep.arc / BMGREP.C < prev    next >
Encoding:
Text File  |  1986-12-09  |  26.3 KB  |  918 lines
  1.  
  2. Relay-Version: version B 2.10.2 9/5/84; site philabs.UUCP
  3. Path: philabs!cmcl2!harvard!talcott!panda!sources-request
  4. From: sources-request@panda.UUCP
  5. Newsgroups: mod.sources
  6. Subject: bm version 1.2 (blindingly fast "fgrep")
  7. Message-ID: <1424@panda.UUCP>
  8. Date: 20 Feb 86 21:44:56 GMT
  9. Date-Received: 21 Feb 86 23:14:56 GMT
  10. Sender: jpn@panda.UUCP
  11. Organization: Bell-Northern Research, Ottawa, Ontario
  12. Lines: 896
  13. Approved: jpn@panda.UUCP
  14.  
  15. Mod.sources:  Volume 4, Issue 1
  16. Submitted by: decvax!bnr-vpa!pdbain (Peter Bain)
  17.  
  18.  
  19. This contains version 1.2 bm.   Differences from 1.1 include certain
  20. bug fixes, notably the one which prevented it from finding patterns
  21. in lines which straddled buffer boundaries.
  22.  
  23. Please see the README for system dependencies.
  24.  
  25. ********************** cut here *******************
  26. #!/bin/sh
  27. # This is a shell archive, meaning:
  28. # 1. Remove everything above the #!/bin/sh line.
  29. # 2. Save the resulting text in a file.
  30. # 3. Execute the file with /bin/sh (not csh) to create the files:
  31. #    bm.h
  32. #    bm.c
  33. #    Execute.c
  34. #    Extern.h
  35. #    GetPatFile.c
  36. #    Global.c
  37. #    MakeDesc.c
  38. #    MakeSkip.c
  39. #    MatchFound.c
  40. #    MkDescVec.c
  41. #    MoveResidue.c
  42. #    PrintLine.c
  43. #    PutUsage.c
  44. #    Search.c
  45. #    Makefile
  46. #    README
  47. #    bm.1
  48. # This archive created: Thu Feb 13 09:21:33 1986
  49. export PATH; PATH=/bin:$PATH
  50. if test -f 'bm.h'
  51. then
  52.     echo shar: over-writing existing file "'bm.h'"
  53. fi
  54. cat << \SHAR_EOF > 'bm.h'
  55. #define FIRSTCHAR ' '
  56. #define MAXCHAR 0377
  57. #define MAXBUFF 8192
  58. #define MAXSIZE 100
  59. #define MAXPATS 100 /* max number of patterns */
  60. #define PSIZEDEF 1024 /* space for patterns if they come from a tty */
  61. #define min(x,y) ((x) < (y) ? (x) : (y))
  62. #define max(x,y) ((x) > (y) ? (x) : (y))
  63. struct PattDesc {
  64.     short unsigned int *Skip1, *Skip2; /* pointers to skip tables */
  65.     char *Pattern;
  66.     int PatLen; /* pattern length */
  67.     char *Start;
  68.     /* starting position of search (at beginning of pattern) */
  69.     int Success; /* true when pattern found */
  70. };
  71. SHAR_EOF
  72. if test -f 'bm.c'
  73. then
  74.     echo shar: over-writing existing file "'bm.c'"
  75. fi
  76. cat << \SHAR_EOF > 'bm.c'
  77. #include <stdio.h>
  78. #include <fcntl.h>
  79. #include <string.h>
  80. #include "bm.h"
  81. #include "Extern.h"
  82. main(argc,argv)
  83. int argc;
  84. char *argv[];
  85. {
  86.     /* grep based on Boyer-Moore algorithm */
  87.     char BigBuff[MAXBUFF + 2];
  88.     /*
  89.     * We leave one extra character at the beginning and end of the buffer,
  90.     * but don't tell Execute about it. This is so when someone is
  91.     * scanning the buffer and scans past the end (or beginning)
  92.     * we are still technically in the buffer (picky, but there ARE
  93.     * machines which would complain)
  94.     */
  95.     int ret = 1, /* return code from Execute */
  96.         NotFound = 0,        /* non-zero if file not readable */
  97.         NFiles,
  98.         NPats; /* number of patterns to search for */
  99.     char *FlagPtr,
  100.         **OptPtr; /* used to scan command line */
  101.     int TextFile /* file to search */;
  102.     struct PattDesc *DescVec[MAXPATS];
  103.  
  104.     --argc;
  105.     OptPtr = argv + 1;
  106.     while ( argc && **OptPtr == '-') {
  107.         FlagPtr = *OptPtr + 1;
  108.         do { 
  109.             switch (*FlagPtr) {
  110.                 case 'c': cFlag = 1; break;
  111.                 case 'e': eFlag = 1;
  112.                     /* get the patterns from next arg */
  113.                     NPats = MkDescVec(DescVec,*++OptPtr);
  114.                     --argc;
  115.                     break;
  116.                 case 'f': fFlag = 1; 
  117.                     /* read the patterns from a file */
  118.                     NPats = GetPatFile(*++OptPtr,DescVec);
  119.                     --argc;
  120.                     break;
  121.                 case 'l': lFlag = 1; break;
  122.                 case 'n': nFlag = 1; break;
  123.                 case 's': sFlag = 1; break;
  124.                 case 'x': xFlag = 1; break;
  125.                 case 'h': hFlag = 1; break;
  126.                 default:
  127.                     fprintf(stderr,
  128.                     "bm: invalid option: -%c \n",
  129.                     *FlagPtr);
  130.                     PutUsage();
  131.                     exit(2);
  132.             } /* switch */
  133.             ++FlagPtr;
  134.         } while (*FlagPtr);
  135.         ++OptPtr; --argc;
  136.     } /* while */
  137.     /* OptPtr now points to patterns */
  138.     if (!fFlag && !eFlag) {
  139.         if (!argc) {
  140.             fprintf(stderr,"bm: no pattern specified\n");
  141.             PutUsage();
  142.             exit(2);
  143.         } else
  144.             NPats = MkDescVec(DescVec,*OptPtr);
  145.         ++OptPtr; --argc;
  146.     }
  147.     /* OptPtr now points to first file */
  148.     NFiles = argc;
  149.     if (!NFiles)
  150.         ret &= Execute(DescVec,NPats,0,BigBuff+1);
  151.     else while (argc--) {
  152.         if ((NFiles > 1) || lFlag) FileName = *OptPtr;
  153.         if ((TextFile = open(*OptPtr,O_RDONLY,0)) < 0) {
  154.             fprintf(stderr,"bm: can't open %s\n",*OptPtr);
  155.             NotFound++;
  156.         }
  157.         else {
  158.             ret &= Execute(DescVec,NPats,TextFile,BigBuff+1);
  159.             if (sFlag && !ret)
  160.                 exit(0);
  161.             close(TextFile);
  162.         } /* if */
  163.         ++OptPtr;
  164.     } /* while */
  165.     if (cFlag) printf("%d\n",MatchCount);
  166.     exit(NotFound ? 2 : ret);
  167. } /* main */
  168. SHAR_EOF
  169. if test -f 'Execute.c'
  170. then
  171.     echo shar: over-writing existing file "'Execute.c'"
  172. fi
  173. cat << \SHAR_EOF > 'Execute.c'
  174. #include <stdio.h>
  175. #include "bm.h"
  176. #include "Extern.h"
  177. Execute(DescVec, NPats, TextFile, Buffer)
  178. register struct PattDesc *DescVec[];
  179. /* pointers to status vectors for the different
  180.     * patterns, including skip tables, position in buffer, etc. */
  181. register int NPats; /* number of patterns */
  182. register char Buffer[]; /* holds text from file */
  183. register int TextFile; /* file to search */
  184. {
  185.     int NRead, /* number of chars read from file */
  186.         NWanted, /* number of chars wanted */
  187.         NAvail, /* number of chars actually read */
  188.         BuffSize, /* number of chars in buffer */
  189.         BuffPos, /* offset of first char in Buffer in TextFile */
  190.         BuffEx, /* flag to indicate that buffer has been searched */
  191.         ResSize,
  192.         /* number of characters in the last, incomplete line */
  193.         Found, /* flag indicates whether pattern found
  194.         * completely and all matches printed */
  195.         Valid; /* was the match "valid", i.e. if -x used,
  196.         * did the whole line match? */
  197.     char *BuffEnd; /* pointer to last char of last complete line */
  198.  
  199.     /* misc working variables */
  200.     int i;
  201.  
  202.     /* initialize */
  203.     ResSize = 0;
  204.     Found = 0;
  205.     BuffPos = 0;
  206.     for (i=0; i < NPats; i++) {
  207.         DescVec[i] -> Success = 0;
  208.         DescVec[i] -> Start = Buffer;
  209.     } /* for */
  210.     /* now do the searching */
  211.     do {
  212.         /* first, read a bufferfull and set up the variables */
  213.         NWanted = MAXBUFF - ResSize; NRead = 0;
  214.         do {
  215.             NAvail =
  216.                read(TextFile,Buffer + ResSize + NRead, NWanted);
  217.             if (NAvail == -1) {
  218.                 fprintf(stderr,
  219.                   "bm: error reading from input file\n");
  220.                 exit(2);
  221.             } /* if */
  222.             NRead += NAvail; NWanted -= NAvail;
  223.         } while (NAvail && NWanted);
  224.         BuffEx = 0;
  225.         BuffSize = ResSize + NRead;
  226.         BuffEnd = Buffer + BuffSize - 1;
  227.         /* locate the end of the last complete line */
  228.         while (*BuffEnd != '\n' && BuffEnd >= Buffer)
  229.             --BuffEnd;
  230.         if (BuffEnd < Buffer)
  231.             BuffEnd = Buffer + BuffSize - 1;
  232.         while (!BuffEx) { /* work through one buffer full */
  233.             BuffEx = 1; /* set it provisionally, then clear
  234.             * it if we find the buffer non-empty */
  235.             for (i=0; i< NPats; i++) {
  236.                 if (!DescVec[i]->Success)
  237.                 /* if the pattern  has not been found */
  238.                     DescVec[i]-> Success =
  239.                     Search(DescVec[i]->Pattern,
  240.                     DescVec[i]->PatLen, BuffEnd,
  241.                     DescVec[i]->Skip1, DescVec[i]->Skip2,
  242.                     DescVec[i]);
  243.                 if (DescVec[i]->Success){
  244.                 /* if a match occurred */
  245.                     BuffEx = 0;
  246.                     Valid = MatchFound(DescVec[i],BuffPos,
  247.                     Buffer, BuffEnd);
  248.                     Found |= Valid;
  249.                     if ((sFlag || lFlag) && Found)
  250.                         return(0);
  251.                 } /* if */
  252.             } /* for */
  253.         } /* while */
  254.         if(NRead) {
  255.             ResSize = MoveResidue(DescVec,NPats,Buffer,
  256.             Buffer+BuffSize-1);
  257.             BuffPos += BuffSize - ResSize;
  258.         } /* if */
  259.     } while (NRead);
  260.     return(!Found);
  261. } /* Execute */
  262. SHAR_EOF
  263. if test -f 'Extern.h'
  264. then
  265.     echo shar: over-writing existing file "'Extern.h'"
  266. fi
  267. cat << \SHAR_EOF > 'Extern.h'
  268. /* global flags for bm */
  269. extern int    cFlag, /* true if we want only a count of matching lines */
  270.     eFlag, /* indicates that next argument is the pattern */
  271.     fFlag, /* true if the patterns arew to come from a file */
  272.     lFlag, /* true if we want a list of files containing the pattern */
  273.     nFlag, /* true if we want the character offset of the pattern */
  274.     sFlag, /* true if we want silent mode */
  275.     xFlag, /* true if we want only lines which match entirely */
  276.     hFlag, /* true if we want no filenames in output */
  277.  
  278.     MatchCount; /* count of number of times a search string was found
  279.     * in the text */
  280. extern char *FileName;
  281. SHAR_EOF
  282. if test -f 'GetPatFile.c'
  283. then
  284.     echo shar: over-writing existing file "'GetPatFile.c'"
  285. fi
  286. cat << \SHAR_EOF > 'GetPatFile.c'
  287. #include <stdio.h>
  288. #include <sys/types.h>
  289. #include <sys/stat.h>
  290. #include "bm.h"
  291. int
  292. GetPatFile(PatFile, DescVec)
  293. char *PatFile;
  294. struct PattDesc *DescVec[];
  295. /* read patterns from a file and set up a pattern descriptor vector */
  296. {
  297.     extern char *malloc();
  298.     FILE *PFile;
  299.     struct stat StatBuff;
  300.     int PatSize; /* the number of chars in all the patterns */
  301.     char *PatBuff; /* hold the patterns */
  302.     if (!(strlen(PatFile))) {
  303.         fprintf(stderr,"bm: no pattern file given\n");
  304.         exit(2);
  305.     } /* if */
  306.     if (!(PFile = fopen(PatFile,"r"))) {
  307.         fprintf(stderr,"bm: can't open pattern file %s\n",PatFile);
  308.         exit(2);
  309.     } /* if */
  310.     /* find out how big the patterns are */
  311.     if (fstat(fileno(PFile),&StatBuff) == -1) {
  312.         fprintf(stderr,"bm: can't fstat %s\n",PatFile);
  313.         exit(2);
  314.     } /* if */
  315.     if (isatty(fileno(PFile)))
  316.         PatSize = PSIZEDEF;
  317.     else PatSize = StatBuff.st_size;
  318.     if (!PatSize) {
  319.         fprintf(stderr,"bm: pattern file is empty\n");
  320.         exit(2);
  321.     } /* if */
  322.     if (!(PatBuff = malloc(PatSize+1))) {
  323.            fprintf(stderr,"bm: insufficient memory to store patterns\n");
  324.         exit(2);
  325.     } /* if */
  326.     fread(PatBuff,1,PatSize,PFile); /* get the patterns */
  327.     /* make sure the patterns are null-terminated. We can't have
  328.     * nulls in the patterns */
  329.     if (PatBuff[PatSize-1] == '\n')
  330.         PatBuff[PatSize-1] = '\0';
  331.     else
  332.         PatBuff[PatSize] = '\0';
  333.     fclose(PFile);
  334.     return(MkDescVec(DescVec,PatBuff));
  335. } /* GetPatFile */
  336. SHAR_EOF
  337. if test -f 'Global.c'
  338. then
  339.     echo shar: over-writing existing file "'Global.c'"
  340. fi
  341. cat << \SHAR_EOF > 'Global.c'
  342. /* global flags for bm */
  343. int    cFlag=0, /* true if we want only a count of matching lines */
  344.     eFlag=0, /* indicates that next argument is the pattern */
  345.     fFlag=0, /* true if the patterns are to come from a file */
  346.     lFlag=0, /* true if we want a list of files containing the pattern */
  347.     nFlag=0, /* true if we want the character offset of the pattern */
  348.     sFlag=0, /* true if we want silent mode */
  349.     xFlag=0, /* true if we want only lines which match entirely */
  350.     hFlag=0, /* true if we want no filenames in output */
  351.  
  352.     MatchCount=0; /* count of number of times a search string was found
  353.     * in the text */
  354. char *FileName = 0;
  355. SHAR_EOF
  356. if test -f 'MakeDesc.c'
  357. then
  358.     echo shar: over-writing existing file "'MakeDesc.c'"
  359. fi
  360. cat << \SHAR_EOF > 'MakeDesc.c'
  361. #include <stdio.h>
  362. #include "bm.h"
  363. #include "Extern.h"
  364. extern char * malloc();
  365. /* makes a pattern descriptor */
  366. struct PattDesc *MakeDesc(Pattern)
  367. char *Pattern;
  368. {
  369.     struct PattDesc *Desc;
  370.     Desc = (struct PattDesc *) malloc(sizeof(struct PattDesc));
  371.     if (!(Desc->Skip1 = (unsigned short int *)
  372.     malloc( sizeof(int) * (MAXCHAR + 1)))){
  373.         fprintf(stderr,"bm: can't allocate space\n");
  374.         exit(2);
  375.     } /* if */
  376.     if (!(Desc->Skip2 = (unsigned short int *)
  377.     malloc(sizeof(int) * strlen(Pattern)))){
  378.         fprintf(stderr,"bm: can't allocate space\n");
  379.         exit(2);
  380.     } /* if */
  381.     Desc->Pattern=Pattern;
  382.     Desc->PatLen = strlen(Desc->Pattern);
  383.     MakeSkip(Desc->Pattern,Desc->Skip1,
  384.     Desc->Skip2,Desc->PatLen);
  385.     return(Desc);
  386. } /* main */
  387. SHAR_EOF
  388. if test -f 'MakeSkip.c'
  389. then
  390.     echo shar: over-writing existing file "'MakeSkip.c'"
  391. fi
  392. cat << \SHAR_EOF > 'MakeSkip.c'
  393. #include <stdio.h>
  394. #include "bm.h"
  395. extern char *malloc();
  396.  
  397. MakeSkip(Pattern,Skip1,Skip2,PatLen)
  398. char Pattern[];
  399. unsigned short int Skip1[], Skip2[];
  400. int PatLen;
  401. /* generate the skip tables for Boyer-Moore string search algorithm.
  402. * Skip1 is the skip depending on the character which failed to match
  403. * the pattern, and Skip2 is the skip depending on how far we got into
  404. * the pattern. Pattern is the search pattern and PatLen is strlen(Pattern) */
  405. {
  406.     int *BackTrack; /* backtracking table for t when building skip2 */
  407.     int c; /* general purpose constant */
  408.     int j,k,t,tp; /* indices into Skip's and BackTrack */
  409.  
  410.     if (!(BackTrack = (int *) malloc(PatLen * (sizeof (int))))){
  411.         fprintf(stderr,"bm: can't allocate space\n");
  412.         exit(2);
  413.     } /* if */
  414.     for (c=0; c<=MAXCHAR; ++c)
  415.         Skip1[c] = PatLen;
  416.     for (k=0;k<PatLen;k++) {
  417.         Skip1[Pattern[k]] = PatLen - k - 1;
  418.         Skip2[k] = 2 * PatLen - k - 1;
  419.     } /* for */
  420.     for (j=PatLen - 1,t=PatLen;j >= 0; --j,--t) {
  421.         BackTrack[j] = t;
  422.         while (t<PatLen && Pattern[j] != Pattern[t]) {
  423.             Skip2[t] = min(Skip2[t], PatLen - j - 1);
  424.             t = BackTrack[t];
  425.         } /* while */
  426.     } /* for */
  427.     for (k=0;k<=t;++k)
  428.         Skip2[k] = min(Skip2[k],PatLen+t-k);
  429.     tp=BackTrack[t];
  430.     while(tp<PatLen) {
  431.         while(t<PatLen) {
  432.             Skip2[t] = min(Skip2[t],tp-t+PatLen);
  433.             ++t;
  434.         } /* while */
  435.         tp = BackTrack[tp];
  436.     } /* while */
  437.     cfree(BackTrack);
  438. } /* MakeSkip */
  439. SHAR_EOF
  440. if test -f 'MatchFound.c'
  441. then
  442.     echo shar: over-writing existing file "'MatchFound.c'"
  443. fi
  444. cat << \SHAR_EOF > 'MatchFound.c'
  445. #include <stdio.h>
  446. #include "bm.h"
  447. #include "Extern.h"
  448. MatchFound(Desc, BuffPos, Buffer, BuffEnd)
  449. struct PattDesc *Desc; /* state info about search for one string */
  450. int BuffPos; /* offset of first char of buffer into the file being searched */
  451. char *Buffer, /* pointer to the first character in the buffer */
  452.     *BuffEnd; /* pointer to the last character in the buffer */
  453. {
  454.     char *MLineBegin, *MLineEnd;
  455.     Desc->Success = 0;
  456.     /* Start points to first character after a successful match */
  457.     MLineBegin = MLineEnd = Desc->Start - 1;
  458.     while(MLineBegin >=Buffer && *MLineBegin != '\n') --MLineBegin;
  459.     ++MLineBegin;
  460.     while( MLineEnd <= BuffEnd && *MLineEnd != '\n') ++MLineEnd;
  461.     if (MLineEnd > BuffEnd) --MLineEnd;
  462.     /* fixed 25jun85 pdbain. suppress multiple matches of the same
  463.     * pattern on one line */
  464.     Desc->Start = MLineEnd + 1;
  465.     /* check if exact match */
  466.     if (xFlag && !( Desc->PatLen == (*MLineEnd != '\n' ? ((MLineEnd -
  467.     MLineBegin) + 1) : (MLineEnd - MLineBegin))))
  468.         return(0); /* failure */
  469.     if (sFlag) return(1);
  470.     if (cFlag) {
  471.         ++MatchCount;
  472.         return(1);
  473.     } /* if */
  474.     PrintLine(BuffPos+(Desc->Start-Buffer),MLineBegin,MLineEnd);
  475.     return(1);
  476. } /* MatchFound */
  477. SHAR_EOF
  478. if test -f 'MkDescVec.c'
  479. then
  480.     echo shar: over-writing existing file "'MkDescVec.c'"
  481. fi
  482. cat << \SHAR_EOF > 'MkDescVec.c'
  483. #include "bm.h"
  484. #include <string.h>
  485. /* scan a newline-separated string of patterns and set up the
  486. * vector of descriptors, one pattern descriptor per pattern. 
  487. * Return the number of patterns */
  488. int
  489. MkDescVec(DescVec, Pats)
  490. struct PattDesc *DescVec[];
  491. char *Pats;
  492. {
  493.     int NPats = 0;
  494.     char *EndPat;
  495.     extern struct PattDesc *MakeDesc();
  496. /* some systems use "strchr" instead of "index" */
  497. /* while (*Pats && (EndPat = index(Pats,'\n')) && NPats < MAXPATS) { */
  498.     while (*Pats && (EndPat = strchr(Pats,'\n')) && NPats < MAXPATS) {
  499.         *EndPat = '\0';
  500.         DescVec[NPats] = MakeDesc(Pats);
  501.         Pats = EndPat + 1;
  502.         ++NPats;
  503.     } /* while */
  504.     if (*Pats && NPats < MAXPATS) {
  505.         DescVec[NPats] = MakeDesc(Pats);
  506.         ++NPats;
  507.     } /* if */
  508.     return(NPats);
  509. } /* MkDescVec */
  510. SHAR_EOF
  511. if test -f 'MoveResidue.c'
  512. then
  513.     echo shar: over-writing existing file "'MoveResidue.c'"
  514. fi
  515. cat << \SHAR_EOF > 'MoveResidue.c'
  516. #include "bm.h"
  517. /* Moves the text which has not been completely searched at the end of
  518. * the buffer to the beginning of the buffer
  519. * and returns number of bytes moved */
  520. int MoveResidue(DescVec, NPats,Buffer, BuffEnd)
  521. struct PattDesc *DescVec[];
  522. int NPats;
  523. char *Buffer, *BuffEnd;
  524. {
  525.     char *FirstStart, *Residue;
  526.     /* use this declaration if you don't use "bcopy" */
  527.     register char *f, *t;
  528.     int ResSize, i;
  529.     FirstStart = BuffEnd;
  530.     /* find the earliest point which has not been
  531.     * completely searched */
  532.     for (i=0; i < NPats; i++) {
  533.         FirstStart = 
  534.             min(FirstStart, DescVec[i]-> Start );
  535.     } /* for */
  536.     /* now scan to the beginning of the line containing the
  537.     * unsearched text */
  538.     for (Residue = FirstStart; *Residue != '\n' &&
  539.     Residue >= Buffer; Residue--);
  540.     if (Residue < Buffer)
  541.         Residue = FirstStart;
  542.     else ++Residue;
  543.     ResSize = (BuffEnd - Residue + 1);
  544.     /* now move the residue to the beginning of
  545.     * the file */
  546.     /* use this if you don't have "bcopy" */
  547.     t = Buffer; f = Residue;
  548.     for(i=ResSize;i;--i)
  549.         *t++ = *f++;
  550.     /* use this if you do have "bcopy" 
  551.     bcopy(Residue, Buffer, ResSize);
  552.     */
  553.     /* now fix the status vectors */
  554.     for (i=0; i < NPats; i++) {
  555.         DescVec[i]->Start -= (Residue - Buffer );
  556.     } /* for */
  557.     return(ResSize);
  558. } /* MoveResidue */
  559. SHAR_EOF
  560. if test -f 'PrintLine.c'
  561. then
  562.     echo shar: over-writing existing file "'PrintLine.c'"
  563. fi
  564. cat << \SHAR_EOF > 'PrintLine.c'
  565. #include <stdio.h>
  566. #include <string.h>
  567. #include "Extern.h"
  568. PrintLine(OffSet,LineStart,LineEnd)
  569. int OffSet; /* offset of LineStart from beginning of file */
  570. char *LineStart,
  571.     *LineEnd;
  572. {
  573.     char OffStr[80];
  574.     if (lFlag) {
  575.         if (strlen(FileName) > 76) {
  576.             fprintf(stderr,"bm: filename too long\n");
  577.             exit(2);
  578.         } /* if */
  579.         if (strlen(FileName)) {
  580.             sprintf(OffStr,"%s\n",FileName);
  581.             write(1,OffStr,strlen(OffStr));
  582.         } /* if */
  583.         return;
  584.     } /* if */
  585.     if (FileName && !hFlag) {
  586.         if (strlen(FileName) > 76) {
  587.             fprintf(stderr,"bm: filename too long\n");
  588.             exit(2);
  589.         } /* if */
  590.         sprintf(OffStr,"%s:",FileName);
  591.         write(1,OffStr,strlen(OffStr));
  592.     } /* if */
  593.     if (nFlag) {
  594.         sprintf(OffStr,"%d: ",OffSet);
  595.         write(1,OffStr,strlen(OffStr));
  596.     } /* if */
  597.     write(1,LineStart,LineEnd-LineStart+1); 
  598.     if (*LineEnd != '\n') write (1,"\n",1);
  599.  } /* PrintLine */
  600. SHAR_EOF
  601. if test -f 'PutUsage.c'
  602. then
  603.     echo shar: over-writing existing file "'PutUsage.c'"
  604. fi
  605. cat << \SHAR_EOF > 'PutUsage.c'
  606. #include <stdio.h>
  607. PutUsage()
  608. {
  609.     fprintf(stderr,
  610.     "bm: search for a given string or strings in a file or files\n");
  611.     fprintf(stderr,
  612.     "synopsis: bm [option]* [string(s)] [file]*\n");
  613.     fprintf(stderr,
  614.     "options:\n");
  615.     fprintf(stderr,
  616.     "-c print only a count of matching lines \n");
  617.     fprintf(stderr,
  618.     "-e Take next argument as the pattern\n");
  619.     fprintf(stderr,
  620.     "-f PFile read patterns from a file PFile\n");
  621.     fprintf(stderr,
  622.     "-h Do not print file names\n");
  623.     fprintf(stderr,
  624.     "-l print a list of files containing the pattern(s) \n");
  625.     fprintf(stderr,
  626.     "-n print the character offset of the pattern(s) \n");
  627.     fprintf(stderr,
  628.     "-s silent mode. Return only success (0) or failure (1)\n");
  629.     fprintf(stderr,
  630.     "-x print only lines which match entirely \n");
  631. } /*PutUsage */
  632. SHAR_EOF
  633. if test -f 'Search.c'
  634. then
  635.     echo shar: over-writing existing file "'Search.c'"
  636. fi
  637. cat << \SHAR_EOF > 'Search.c'
  638. #include "bm.h"
  639. #include "Extern.h"
  640. int Search(Pattern,PatLen,EndBuff, Skip1, Skip2, Desc)
  641. register char Pattern[];
  642. int PatLen;
  643. char *EndBuff;
  644. unsigned short int Skip1[], Skip2[];
  645. struct PattDesc *Desc;
  646. {
  647.     register char *k, /* indexes text */
  648.         *j; /* indexes Pattern */
  649.     register int Skip; /* skip distance */
  650.     char *PatEnd,
  651.     *BuffEnd; /* pointers to last char in Pattern and Buffer */
  652.     BuffEnd = EndBuff;
  653.     PatEnd = Pattern + PatLen - 1;
  654.  
  655.     k = Desc->Start;
  656.     Skip = PatLen-1;
  657.     while ( Skip <= (BuffEnd - k) ) {
  658.         j = PatEnd;
  659.         k = k + Skip;
  660.         while (*j == *k) {
  661.             if (j == Pattern) {
  662.                 /* found it. Start next search
  663.                 * just after the pattern */
  664.                 Desc -> Start = k + Desc->PatLen;
  665.                 return(1);
  666.             } /* if */
  667.             --j; --k;
  668.         } /* while */
  669.         Skip = max(Skip1[*(unsigned char *)k],Skip2[j-Pattern]);
  670.     } /* while */
  671.     Desc->Start = k+Skip-(PatLen-1);
  672.     return(0);
  673. } /* Search */
  674. SHAR_EOF
  675. if test -f 'Makefile'
  676. then
  677.     echo shar: over-writing existing file "'Makefile'"
  678. fi
  679. cat << \SHAR_EOF > 'Makefile'
  680. CCFLAGS =  -O 
  681. SOURCES =  bm.h bm.c Execute.c Extern.h\
  682.     GetPatFile.c Global.c MakeDesc.c MakeSkip.c \
  683.     MatchFound.c \
  684.     MkDescVec.c MoveResidue.c PrintLine.c PutUsage.c Search.c
  685. OBJECTS = bm.o Execute.o \
  686.     GetPatFile.o Global.o MakeDesc.o MakeSkip.o \
  687.     MatchFound.o \
  688.     MkDescVec.o MoveResidue.o Search.o PrintLine.o PutUsage.o
  689. BASEFILES = $(SOURCES) Makefile README bm.1
  690. bm: $(OBJECTS)
  691.     cc -s -o bm $(CCFLAGS) $(OBJECTS)
  692. install: bm
  693.     rm -f /usr/bin/bm
  694.     cp bm /usr/bin/bm
  695.     chmod ugo-w /usr/bin/bm
  696. #    rm /usr/src/public/bm/*
  697. #    cp $(BASEFILES) /usr/src/public/bm
  698. shar:
  699.     /usr/local/bin/shar $(BASEFILES) >bm.shar
  700. man: /usr/man/man1/bm.1
  701. /usr/man/man1/bm.1: bm.1
  702.     rm -f /usr/man/man1/bm.1
  703.     cp bm.1 /usr/man/man1/bm.1
  704.     man bm > /dev/null
  705. bm.o: bm.c bm.h Extern.h
  706.     cc -c $(CCFLAGS) bm.c
  707. PutUsage.o: PutUsage.c bm.h 
  708.     cc -c $(CCFLAGS) PutUsage.c
  709. MakeSkip.o: MakeSkip.c bm.h 
  710.     cc -c $(CCFLAGS) MakeSkip.c
  711. Search.o: Search.c bm.h Extern.h
  712.     cc -c $(CCFLAGS) Search.c
  713. Execute.o: Execute.c bm.h 
  714.     cc -c $(CCFLAGS) Execute.c
  715. MoveResidue.o: MoveResidue.c bm.h Extern.h
  716.     cc -c $(CCFLAGS) MoveResidue.c
  717. MatchFound.o: MatchFound.c bm.h Extern.h
  718.     cc -c $(CCFLAGS) MatchFound.c
  719. PrintLine.o: PrintLine.c Extern.h
  720.     cc -c $(CCFLAGS) PrintLine.c
  721. MkDescVec.o: MkDescVec.c bm.h
  722.     cc -c $(CCFLAGS) MkDescVec.c
  723. GetPatFile.o: GetPatFile.c bm.h
  724.     cc -c $(CCFLAGS) GetPatFile.c
  725. MakeDesc.o: MakeDesc.c bm.h
  726.     cc -c $(CCFLAGS) MakeDesc.c
  727. Global.o: Global.c
  728.     cc -c $(CCFLAGS) Global.c
  729. listing:
  730. # use -o for Sys V, -i for 4.2BSD
  731. #    print -i3 $(BASEFILES)
  732.     print -o3 $(BASEFILES)
  733. clean:
  734.     rm -f *.o a.out foo bar blat junk core
  735. SHAR_EOF
  736. if test -f 'README'
  737. then
  738.     echo shar: over-writing existing file "'README'"
  739. fi
  740. cat << \SHAR_EOF > 'README'
  741. Bm is a fast pattern matching utility, intended to be almost
  742. identical in functionality to fgrep (ugh!) but much faster. It uses
  743. the Boyer-Moore algorithm, as described in the papers listed below:
  744.  
  745. D.E. Knuth, J.H. Morris, V.R. Pratt,"Fast Pattern Matching in Strings", 
  746. SIAM J. Comput., 6(2), June  1977, 323-350, 
  747.  
  748. Z. Galil,
  749. "On Improving the Worst Case Running Time of the Boyer-Moore String
  750. Matching Algorithm", 
  751. CACM, 22(9), Sept. 1979, ACM, 
  752.  
  753. R.S. Boyer, J.S. Moore,"A Fast String Searching Algorithm", CACM, 20(10), 
  754. Oct. 1977, 762-772, 
  755.  
  756. G. de V. Smit,"A Comparison of Three String Matching Algorithms", 
  757. Software - Practice and Experience, vol. 12,  1982, 57-66, 
  758.  
  759. *** NOTE *** There are certain system dependencies in the code.
  760. Please check whether your system uses "index" or "strchr" to
  761. find a character in a string: this affects MkDescVec.c.
  762. Also check whether your system uses <strings.h> or <string.h>.
  763. This affects match.c/bm.c, MkDescVec.c, and PrintLine.c.
  764. Also check whether your system has "bcopy". If so, see MoveResidue.c
  765.  
  766. The files are MkDescVec.c, PrintLine.c, bm.c, and 
  767. Execute.c: search a file for the patterns
  768. Extern.h: declarations of externs
  769. GetPatFile.c: read in patterns from a file and set up a vector of
  770.     pattern descriptors
  771. Global.c: global variables (complement to Extern.h)
  772. MakeDesc.c: create a pattern descriptor for one pattern, including
  773.     skip tables, etc.
  774. MakeSkip.c: make the skip tables for one pattern
  775. Makefile: you can figure this one out for yourself
  776. MatchFound.c: what to do when you actually FIND a pattern - print it,
  777.     update flags, etc.
  778. MkDescVec.c: make a vector of pattern descriptors, given a string
  779.     of newline-separated patterns
  780. MoveResidue.c: when you come to the end of the buffer, move the
  781.     unsearched "residue" to the beginning and start again
  782. PrintLine.c: print the appropriate stuff after finding a match
  783. PutUsage.c: mini-man page.
  784. README: this file
  785. Search.c: the guts. Implements B-M algorithm given a pattern, skip
  786.     tables for the pattern, and a buffer to search
  787. bm.c: mainline. mostly interpreting the command line and tidying
  788.     up at the end. Calls Execute for each file.
  789. bm.h: constants
  790. bm.p: man page
  791. SHAR_EOF
  792. if test -f 'bm.1'
  793. then
  794.     echo shar: over-writing existing file "'bm.1'"
  795. fi
  796. cat << \SHAR_EOF > 'bm.1'
  797. .TH BM (1) "8 July 1985"
  798. .UC 4
  799. .SH NAME
  800. bm \- search a file for a string
  801. .SH SYNOPSIS
  802. .B /usr/bin/bm
  803. [ option ] ...
  804. [ strings ]
  805. [ file ]
  806. .SH DESCRIPTION
  807. .I Bm
  808. searches the input
  809. .I files
  810. (standard input default) for lines matching a string.
  811. Normally, each line found is copied to the standard output.
  812. It is blindingly fast.
  813. .I Bm
  814. strings are fixed sequences of characters:
  815. there are no wildcards, repetitions, or other features
  816. of regular expressions.
  817. Bm is also case sensitive.
  818. The following options are recognized.
  819. .TP
  820. .B \-x
  821. (Exact) only lines matched in their entirety are printed
  822. .TP
  823. .B \-l
  824. The names of files with matching lines are listed (once) separated by newlines.
  825. .TP
  826. .B \-c
  827. Only a count of the number of matches
  828. is printed
  829. .TP
  830. .B \-e "string"
  831. The string is the next argument after the
  832. .B \-e
  833. flag. This allows strings beginning with '-'.
  834. .TP
  835. .B \-h
  836. No filenames are printed, even if multiple files are searched.
  837. .TP
  838. .B \-n
  839. Each line is preceded by the number
  840. of characters from the beginning of the file
  841. to the match.
  842. .TP
  843. .B \-s
  844. Silent mode.  Nothing is printed (except error messages).
  845. This is useful for checking the error status.
  846. .TP
  847. .BI \-f " path"
  848. The string list
  849. is taken from the
  850. .I path.
  851. This may be either a file or a tty.
  852. .LP
  853. Unless the
  854. .B \-h
  855. option is specified
  856. the file name is shown if there is more than one input file.
  857. Care should be taken when using the characters $ * [ ^ | ( ) and \\ in the
  858. .I strings
  859. (listed on the command line)
  860. as they are also meaningful to the Shell.  It is safest to enclose the entire
  861. .I expression
  862. argument in single quotes \' \'.
  863. .LP
  864. .I Bm
  865. searches for lines that contain one of the (newline-separated)
  866. .I strings,
  867. using
  868. the Boyer-Moore algorithm.
  869. It is far superior in terms of speed to the grep (egrep, fgrep)
  870. family of pattern matchers for fixed-pattern searching,
  871. and its speed increases with pattern length.
  872. .SH "SEE ALSO"
  873. grep(1)
  874. .SH DIAGNOSTICS
  875. Exit status is 0 if any matches are found,
  876. 1 if none, 2 for syntax errors or inaccessible files.
  877. .SH AUTHOR
  878. Peter Bain (pdbain@bnr-vpa), with modifications suggested by John Gilmore
  879. and Amir Plivatsky
  880. .SH BUGS
  881. Only 100 patterns are allowed.
  882. .LP
  883. Patterns may not contain newlines.
  884. .LP
  885. If a line (delimited by newlines, and the beginning and end of the file)
  886. is longer than 8000 charcters (e.g. in a core dump),
  887. it will not be completely printed.
  888. .LP
  889. If multiple patterns are specified, the order of the ouput lines is not
  890. necessarily the same as the order of the input lines.
  891. .LP
  892. A line will be printed once for each different string on that line.
  893. .LP
  894. The algorithm cannot count lines.
  895. .LP
  896. The
  897. .B -n
  898. and
  899. .B -c
  900. work differently from fgrep.
  901. .LP
  902. The
  903. .B -v,
  904. .B -i,
  905. and
  906. .B -b
  907. are not available.
  908. SHAR_EOF
  909. #    End of shell archive
  910. exit 0
  911.  
  912.  
  913. % t argument after the
  914. .B \-e
  915. flag. This allows strings beginning with '-'.
  916. .TP
  917. .B \-h
  918. No filenames are printed,